/*
Palindrome Partitioning
Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

[
["aa","b"],
["a","a","b"]
]
*/

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <fstream>
#include <sstream>
#include <unordered_set>
#include "print.h"
using namespace std;

/**
* Definition for binary tree*/


void testForStack()
{
	stack<int> mystack;
	mystack.push(10);
	mystack.push(20);
	mystack.top() -= 5;
	cout << "mystack.top() is now " << mystack.top() << endl;
}

void testForIntToString()
{
	int a = 10;
	stringstream ss;
	ss << a;
	string str = ss.str();
	cout << str << endl;

	string str1 = to_string(a);

}



class Solution {
public:
	void corePartition(string s, vector<vector<string> > &result, vector<string> &temp)
	{
		if (s.size() <1)
		{
			result.push_back(temp);
			return;
		}

		for (int i = 0; i < s.size(); i++)
		{
			int begin = 0;
			int end = i;
			while (begin<end)
			{
				if (s[begin] == s[end])
				{
					begin++;
					end--;
				}
				else
					break;

			}
			if (begin>=end)
			{
				temp.push_back(s.substr(0,i+1));
				corePartition(s.substr(i+1),result,temp);
				temp.pop_back();
			}
		}


	}
	vector<vector<string>> partition(string s) {
		
		vector<vector<string>> result;
		if (s.size() == 0)
		{
			return result;
		}
		vector<string> temp;
		corePartition(s,result,temp);
		return result;
	}
};





int main(int argc, char* argv[])
{



	string start = "hit";
	string end = "cog";


	//cout << "Input the string" << endl;
	//string str;

	//cin >> str;

	string str = "aab";





	vector<vector<string>> result;



	Solution s;
	result = s.partition(str);
	//stackTree.push(p->left);
	//stackTree.push(p->right);
	//if (s.isPalindrome(str1))
	//	cout << " True" << endl;
	//else
	//	cout << "false" << endl;
	system("pause");
	return 0;
}
//std::unordered_set<std::string> myset =
//{ "hot", "dot", "dog", "lot", "log" };

//std::cout << "myset contains:";
// for (auto it = myset.begin(); it != myset.end(); ++it)
//std::cout << " " << *it;
//;; std::cout << std::endl;

//TreeNode *root = new TreeNode(1);
//TreeNode *left = new TreeNode(2);
//TreeNode *right = new TreeNode(3);

//root->left = left;
//root->right = right;